1. Field of the Invention
The present invention relates to the technical field of finite impulse response filters (FIR) and, more particularly, to a method for implementing a multiplier-less FIR filter based on modified DECOR transformation and a trellis de-allocation scheme.
2. Description of Related Art
Conventionally, the finite impulse response (FIR) filter is one of the key functional blocks in many digital signal processing (DSP) applications. In time domain representation, an N-tap FIR filter performs the following convolution:
                                          y            ⁡                          [              n              ]                                =                                    ∑                              k                =                0                                            N                -                1                                      ⁢                                                  ⁢                                          h                k                            ⁢                              x                ⁡                                  [                                      n                    -                    k                                    ]                                                                    ,                            (        1        )            where hk is the k-th coefficient of the FIR filter; and x(n) and y(n) denote the input and the output signals at time instance n, respectively. Such a FIR filter architecture is shown in FIG. 1. As shown, the multiplicative operation is the fundamental function in the FIR filter structure, which may cause a severe problem because the array multiplier requires a large layout area and tremendous power consumption.
With reference to FIG. 5, there is shown a preferred embodimentof the method for implementing multipler-less FIR filters, which includes the steps of: (Step 1) compressing the dynamic range of filter coefficients into a smaller set; (Step 2) quantizing these pre-processed coefficients, which are generated by step 1, into SPT numbers; and (step 3) optimizing the coefficients by removing redundant SPT numbers.
In such a multiplier-less FIR filter implementation, the number of nonzero digits employed determines the cost of the FIR filter. Therefore, the increase of the number of nonzero digits will increase the hardware complexity. To avoid employing complicated hardware, it is desired to control the number of nonzero digits to be smaller than a predetermined value.
However, FIG. 2 demonstrates the distribution of 2-nonzero-digit SPT numbers between 0.0 and 1.0 for wordlength 7, 8, and 9, respectively As we can see, the gaps of the SPT distribution that exceed 0.5 cannot be reduced even if the wordlength of the SPT numbers increases. To achieve higher precision performance (reducing the gaps), we have to employ more non-zero digits. However, increasing the non-zero digit has the effect of increasing the number of adders in each filter tap.
In the known 1st-order differential coefficient method (DCM), equation (1) can be reformulated as follows:
                                                                        y                ⁡                                  [                  n                  ]                                            =                            ⁢                                                ∑                                      k                    =                    0                                                        N                    -                    1                                                  ⁢                                                      (                                                                                  ⁢                                                                  h                        k                                            -                                              h                                                  k                          -                          1                                                                    +                                              h                                                  k                          -                          1                                                                                      )                                    ⁢                                      x                    ⁡                                          [                                              n                        -                        k                                            ]                                                                                                                                              =                            ⁢                                                                    h                    0                                    ⁢                                      x                    ⁡                                          [                      n                      ]                                                                      +                                                      ∑                                          k                      =                      1                                                              N                      -                      1                                                        ⁢                                                            δ                      k                      1                                        ⁢                                          x                      ⁡                                              [                                                  n                          -                          k                                                ]                                                                                            +                                  y                  ⁡                                      [                                          n                      -                      1                                        ]                                                  -                                                      h                                          N                      -                      1                                                        ⁢                                                            x                      ⁡                                              [                                                  n                          -                          N                                                ]                                                              .                                                                                                          (        2        )            where δ1k≡hk−hk−1. The “1st-order” operation denotes the difference between the contiguous coefficients is taken only once. The corresponding structure of the DCM-based FIR structure is depicted in FIG. 3, wherein the extra cost of the 1st-order DCM is one additional tap and one accumulator, as circled by the dotted line. For m-th-order DCM, the coefficients are generated by taking the difference of the (m−1)th-order DCM coefficients asδmk−m/k≡δm−1k−m+1/k−δm−1k−m/k−1.  (3)
The effectiveness of the DCM reduced the dynamic range of filter coefficient significantly as shown in FIG. 4. The reduction of dynamic range of FIR filter implies that the wordlength can be reduced.
An alternative representation for FIR filter in z-domain is given in Eq. (4). H(z) is named as the transfer function of the filter.
                              H          ⁡                      (            z            )                          =                              ∑                          k              =              0                                      N              -              1                                ⁢                                          ⁢                                    h              k                        ⁢                                          z                                  -                  k                                            .                                                          (        4        )            
From z-domain point of view, it is able to represent the first order DCM of the FIR filter as
                                                        H              ′                        ⁡                          (              z              )                                =                                                    H                ⁡                                  (                  z                  )                                            ⁢                              (                                  1                  -                                      z                                          -                      1                                                                      )                                                    (                              1                -                                  z                                      -                    1                                                              )                                      ,                            (        5        )            where H(z) is the transfer function of original FIR filter. It can be seen that the transfer function is the same as long as the introduced term, (1−z−1), is fully cancelled in both denominator and numerator of Eq. (5). Furthermore, this transformation equivalents to inserting a pole-zero pair on the real axis of z-plane with z=1. For m-th order DCM, m pairs pole and zero are located on the same position. In addition, Eq. (5) can be generalized to the DECOR transformation, in which the transfer function is rewritten as
                                          H            ′                    ⁡                      (            z            )                          =                              H            ⁡                          (              z              )                                ⁢                                                                      (                                      1                    +                                          α                      ⁢                                                                                          ⁢                                              z                                                  -                          β                                                                                                      )                                m                                                              (                                      1                    +                                          α                      ⁢                                                                                          ⁢                                              z                                                  -                          β                                                                                                      )                                m                                      .                                              (        6        )            
The parameters of α and β are chosen depending on the filter type, and m denotes the order (iteration numbers of coefficient operation) of DECOR as listed in Table 1. As known, following DECOR transformation can reduce the coefficient dynamic range in all kinds of FIR filter.
TABLE 1Filter TypeαβF(z)Low-pass−1  1(1 − z−1)mHigh-pass11(1 + z−1)mBand-pass(ωc: center frequency)1π/ωc(1 − z−π/ωc)mBand-stop−1  2(1 − z−2)m
In the design of FIR filter based on the SPT term, quantizing the coefficient after DECOR transformation will encounter the stability problem. Therefore, quantization must be held before DECOR transformation.
This procedure ensures that DECOR based FIR filter can be implemented by shift-and-add operation instead of array multiplier. However, it results in a serious coefficient quantization problem since the filter coefficient may exceed 0.5. Quantizing these coefficients and then transferring them into a smaller dynamic range only helps reduce wordlength but not quantization error. As a result, a DCM and DECOR based FIR filter still needs more nonzero terms to prevent serious quantization problem in quantizing larger coefficients. Therefore, it is desired for the discussed FIR filter to be improved, so as to migrate and/or obviate the aforementioned problem.